package 树与图.字典树;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 104. 二叉树的最大深度
 *
 * 给定一个二叉树 root ，返回其最大深度。
 * 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
 *
 * 思路：
 * 思路1：采用递归的方式，递归求解左右子树的最大深度，然后取最大值+1，返回最大深度。
 *
 * 思路2： 采用迭代的方式，使用BFS，使用队列，每次出队列一个节点，然后分别将左右子树入队列，然后取队列长度的最大值，返回最大深度。
 */
public class L_104 {

    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);

        return Math.max(left,right)+1;
    }

    /**
     * 迭代，BFS遍历
     * @param root
     * @return
     */
    public int maxDepth1(TreeNode root) {
        int depth = 0;
        if(root == null){
            return 0;
        }

        // 创建一个队列实现BFS
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            // 将每一层的节点添加到队列中
            int currentLevelSize = queue.size();
            for (int i = 0; i < currentLevelSize; i++) {
                TreeNode currentNode = queue.poll();
                //添加左右子树
                if(currentNode.left != null){
                    queue.add(currentNode.left);
                }
                if(currentNode.right != null){
                    queue.add(currentNode.right);
                }
            }
            // 当前层级遍历完，层数+1
            depth++;
        }
        return depth;
    }




    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
